#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: code_03.py 
@version:
@time: 2023/08/18 
"""
import sys


def find_max_crossing_subarray(array, mid):
    max_sum = -sys.maxsize - 1
    sum_now = 0
    i = mid
    left = i
    while i >= 0:
        sum_now += array[i]
        if sum_now > max_sum:
            left = i
            max_sum = sum_now
        i -= 1
    left_max = max_sum
    j = mid + 1
    sum_now = 0
    right = j
    max_sum = -sys.maxsize - 1
    while j < len(array):
        sum_now += array[j]
        if sum_now > max_sum:
            right = j
            max_sum = sum_now
        j += 1
    right_max = max_sum
    return array[left:right + 1], left_max + right_max


def find_max_subarray(array):
    if len(array) <= 1:
        return array, array[0]
    left_part = array[0:int(len(array) / 2)]
    right_part = array[int(len(array) / 2):len(array)]
    left_sub_array, left_max = find_max_subarray(left_part)
    right_sub_array, right_max = find_max_subarray(right_part)

    crossing_sub_array, crossing_max = find_max_crossing_subarray(array, int(len(array) / 2) - 1)
    max_sub_array, max_sum = right_sub_array, left_max
    if right_max > left_max:
        max_sub_array, max_sum = right_sub_array, right_max
    if crossing_max > max_sum:
        max_sub_array, max_sum = crossing_sub_array, crossing_max
    return max_sub_array, max_sum


class Practice01:
    def find_max_subarray(self, array):
        if len(array) <= 1:
            return array, array[0]
        left_part = array[0:int(len(array) / 2)]
        right_part = array[int(len(array) / 2):len(array)]
        left_sub_array, left_max = find_max_subarray(left_part)
        right_sub_array, right_max = find_max_subarray(right_part)

        crossing_sub_array, crossing_max = self.find_max_crossing_subarray(array, int(len(array) / 2) - 1)

        max_sub_array, max_sum = left_sub_array, left_max
        if right_max > left_max:
            max_sub_array, max_sum = right_sub_array, right_max
        if crossing_max > max_sum:
            max_sub_array, max_sum = crossing_sub_array, crossing_max
        return max_sub_array, max_sum

    @staticmethod
    def find_max_crossing_subarray(array, mid):
        max_sum = -sys.maxsize - 1

        i = mid
        sum_now = 0
        left = i
        while i >= 0:  # 查找包含left_end的左边子数组
            sum_now += array[i]
            if sum_now > max_sum:
                left = i  # 记录元素和最大时的元素下标
                max_sum = sum_now
            i -= 1
        left_max = max_sum

        max_sum = -sys.maxsize - 1

        j = mid + 1
        sum_now = 0
        right = j
        while j < len(array):
            sum_now += array[j]
            if sum_now > max_sum:
                right = j
                max_sum = sum_now
            j += 1
        right_max = max_sum

        return array[left:right + 1], left_max + right_max


if __name__ == '__main__':
    array = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
    sub_array, max_sum1 = find_max_subarray(array)
    print("the max sub array is {0} and sum is {1}".format(sub_array, max_sum1))
    # practice01
    sub_array, max_sum1 = Practice01().find_max_subarray(array)
    print("the max sub array is {0} and sum is {1}".format(sub_array, max_sum1))


